/*
    该文件实现BPTree.h中定义的函数
*/
#include "BPTree.h"

// 创建一个B+树节点
BPTreeNode* BPTree::NewBPTreeNode() {
    BPTreeNode* node = (BPTreeNode*)malloc(sizeof(BPTreeNode));
    if (node == NULL)
        return NULL;
    for (int index = 0; index < 2 * M - 1; index++)
        node->indexNodes[index].value = -1;
    for (int index = 0; index < 2 * M; index++)
        node->childs[index] = NULL;
    node->num = 0;
    node->isLeaf = true;
    node->prev = NULL;
    node->next = NULL;
    return node;

}

//B+树的创建
BPTreeNode* BPTree::CreateBPTree() {
    BPTreeNode* node = NewBPTreeNode();
    if (NULL == node)
        return NULL;
    node->prev = node;
    node->next = node;
    return node;
}

//创建一个索引节点，即B+树节点中的关键码
IndexNode BPTree::NewIndexNode(const Record& record, int col) {
    IndexNode indexNode;
    indexNode.primaryKey = record.primaryKey;
    indexNode.value = record.recordList[col - 1];
    return indexNode;
}

//节点分裂
int BPTree::NodeSplit(BPTreeNode* parent, int pos, BPTreeNode* child) {
    BPTreeNode* newChild = NewBPTreeNode();
    if (!newChild)
        return -1;
    newChild->isLeaf = child->isLeaf;
    newChild->num = M - 1;
    for (int index = 0; index < M - 1; index++)
        newChild->indexNodes[index] = child->indexNodes[index + M];
    if (!newChild->isLeaf) {
        for (int index = 0; index < M; index++)
            newChild->childs[index] = child->childs[index + M];
    }
    child->num = M - 1;
    if (child->isLeaf)
        child->num++; // 如果是叶节点，保留中间的关键码
    for (int index = parent->num; index > pos; index--)
        parent->childs[index + 1] = parent->childs[index];
    parent->childs[pos + 1] = newChild;
    for (int index = parent->num - 1; index >= pos; index--)
        parent->indexNodes[index + 1] = parent->indexNodes[index];
    parent->indexNodes[pos] = child->indexNodes[M - 1];
    parent->num++;

    // 叶节点情况，需要更新指针
    if (child->isLeaf) {
        newChild->next = child->next;
        child->next->prev = newChild;
        child->next = newChild;
        newChild->prev = child;
    }
    return 1;
}

//插入一个未满的节点中
void BPTree::Insert2NotFull(BPTreeNode * node, const IndexNode& indexNode) {
    if (node->isLeaf) {
        int pos = node->num;
        while (pos >= 1 && indexNode.value < node->indexNodes[pos - 1].value) {
            node->indexNodes[pos] = node->indexNodes[pos - 1];
            pos--;
        }
        node->indexNodes[pos] = indexNode;
        node->num++;
    } else {
        int pos = node->num;
        while (pos > 0 && indexNode.value < node->indexNodes[pos - 1].value) {
            pos--;
        }

        if (2 * M - 1 == node->childs[pos]->num) {
            NodeSplit(node, pos, node->childs[pos]);
            if (indexNode.value > node->indexNodes[pos].value)
                pos++;
        }
        Insert2NotFull(node->childs[pos], indexNode);
    }
}

// 插入节点
BPTreeNode* BPTree::InsertNode(BPTreeNode* root, const Record& record, int col) {
    IndexNode indexNode = NewIndexNode(record, col);
    if (!root) {
        return NULL;
    }
    if (root->num == 2 * M - 1) {
        BPTreeNode* node = NewBPTreeNode();
        if (!node) {
            return NULL;
        }
        node->isLeaf = false;
        node->childs[0] = root;
        NodeSplit(node, 0, root);
        Insert2NotFull(node, indexNode);
        return node;
    } else {
        Insert2NotFull(root, indexNode);
        return root;
    }
}

/* 
    搜索特定属性值
    · root B+树根节点
    · value 属性值
    · result 结果数组 存放记录的主键
    · num 结果数
*/
void BPTree::Search4EqualInterval(BPTreeNode* root, int value, int64_t *result, int &num) {
    num = 0;
    if (!root)
        return;
    BPTreeNode *node = root;
    while (!node->isLeaf) { //不是叶节点，向下搜索
        int pos = 0;
        while (pos < node->num && value > node->indexNodes[pos].value)
            pos++;
        node = node->childs[pos];
    }
    //到达叶节点，顺着next指针往前搜索
    while (node) {
        for (int index = 0; index < node->num && num < MAX_RESULT_NUM; index++) {
            if (node->indexNodes[index].value > value)
                return;
            if (node->indexNodes[index].value == value)
                result[num++] = node->indexNodes[index].primaryKey;
        }
        if (num == MAX_RESULT_NUM)
            return ;
        node = node->next;
    }
}

// 搜索属性值在[lowerBound,upperBound]范围内的记录
void BPTree::Search4Interval(BPTreeNode* root, int lowerBound, int upperBound, int64_t *result, int &num) {
    num = 0;

    BPTreeNode *leftNode = root;
    BPTreeNode *rightNode = root;

    // 往下搜索，到达两个端点所在的叶节点
    while (!leftNode->isLeaf) {
        int pos = 0;
        while (pos < leftNode->num && lowerBound > leftNode->indexNodes[pos].value)
            pos++;
        leftNode = leftNode->childs[pos];
    }
    while (!rightNode->isLeaf) {
        int pos = rightNode->num;
        while (pos > 0 && upperBound < rightNode->indexNodes[pos - 1].value)
            pos--;
        rightNode = rightNode->childs[pos];
    }

    // 移动leftNode指针直到rightNode
    while (leftNode != rightNode) {
        if(leftNode==NULL){
            printf("error\n");
        }
        for (int index = 0; index < leftNode->num && num < MAX_RESULT_NUM; index++) {
            if (leftNode->indexNodes[index].value >= lowerBound)
                result[num++] = leftNode->indexNodes[index].primaryKey;
        }
        if (num == MAX_RESULT_NUM)
            return ;
        leftNode = leftNode ->next;
    }

    // leftNode和rightNode相遇
    for (int index = 0; index < leftNode->num && num < MAX_RESULT_NUM; index++) {
        if (lowerBound <= leftNode->indexNodes[index].value && leftNode->indexNodes[index].value <= upperBound)
            result[num++] = leftNode->indexNodes[index].primaryKey;
    }
}

// 保存为第col列属性创建的B+树，创建或更新索引时调用此函数
void BPTree::SaveBPTree(BPTreeNode *root, int col) {
    char indexPath[20];
    sprintf(indexPath, "%s%d", INDEX_PREFIX, col);
    // 删除原来的索引文件
    if (access(indexPath, F_OK) == 0) {
        if (remove(indexPath ) == -1) {
            printf("删除失败\n");
            throw "In BPlusTree::SaveBPTree(),remove error";
        }
    }
    int fd = open(indexPath, O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
    if (fd == -1)
        throw "In BPlusTree::SaveBPTree(),open error";
    SaveNode2File(fd, root);
    close(fd);
}


// 将B+树节点写入文件
void BPTree::SaveNode2File(int &fd, BPTreeNode *node) {
    if (node == NULL || fd == -1) {
        return ;
    }
    if (write(fd, node, sizeof(BPTreeNode)) == -1)
        throw "In BPTree::SaveNode2File(),write error";
    for (int index = 0; index <= node->num; index++)
        SaveNode2File(fd, node->childs[index]);
}

// 读取B+树
BPTreeNode* BPTree::LoadBPTree(int col) {
    BPTreeNode* preLeafNode = NULL; //保存前一个叶节点
    char indexPath[20];
    sprintf(indexPath, "%s%d", INDEX_PREFIX, col);
    if (access(indexPath, F_OK) == -1)
        return NULL;
    int fd = open(indexPath, O_RDONLY, S_IRUSR | S_IWUSR);
    if (fd == -1)
        return NULL;
    BPTreeNode *node = LoadNode(fd, preLeafNode);
    close(fd);
    return node;
}

// 读取B+树节点
BPTreeNode *BPTree::LoadNode(int &fd, BPTreeNode* &preLeafNode) {

    BPTreeNode *node = NewBPTreeNode();
    if (node == NULL)
        return NULL;
    if (read(fd, node, sizeof(BPTreeNode)) == -1)
        return NULL;
    if (node->isLeaf) {
        if (preLeafNode == NULL)
            preLeafNode = node;
        else
        {
            preLeafNode->next = node;
            preLeafNode = node;
        }
        return node;
    }
    for (int index = 0; index <= node->num; index++)
        node->childs[index] = LoadNode(fd,preLeafNode);
    return node;
}
































